# encoding: utf-8
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: counting_sort.py 
@time: 2019/7/1 17:06
"""
'''
计数排序要求输入数据的范围在 [0,N-1] 之间，则可以开辟一个大小为 N 的数组空间，将输入的数据值转化为键存储在该数组空间中，数组中的元素为该元素出现的个数。它是一种线性时间复杂度的排序。
'''
def countingSort(nums):
    bucket = [0] * (max(nums) + 1)
    # 桶的个数
    for num in nums:
        # 将元素值作为键值存储在桶中,记录其出现的次数
        bucket[num] += 1
    i = 0
    # nums的索引
    for j in range(len(bucket)):
        while bucket[j] > 0:
            nums[i] = j
            bucket[j] -= 1
            i += 1
    return nums

# Example use
nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
print(countingSort(nums))